#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_set"

using namespace std;
/*HJJ QQ479287006
 *491. 递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。



示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]
 * */
vector<vector<int>> ret;
vector<int> temp;

void findSubsequencesBack(vector<int> &nums, int start) {
    if (temp.size() >= 2) {
        ret.push_back(temp);
    }
    unordered_set<int> uset;//这里建立一个会过滤同一层 第几次进入这个函数就是第几层
    for (int i = start; i < nums.size(); ++i) {

        //去除本层元素以及 保证前一个元素大于后面一个 注意用empty 好点 temp.back() 获取最后那个元素
        if ((!temp.empty() && temp.back() > nums[i]) || uset.find(nums[i]) != uset.end())
            continue;
        uset.insert(nums[i]); // 记录这个元素在本层⽤过了，本层后⾯不能再⽤了

        temp.push_back(nums[i]);
        findSubsequencesBack(nums, i + 1);
        temp.pop_back();
    }
}
//vector<int> used; 这个好像还不能用来used那个
//void findSubsequencesBack1(vector<int> &nums, int start) {
//    if (temp.size() >= 2) {
//        ret.push_back(temp);
//    }
//    //unordered_set<int> uset;//这里建立一个会过滤同一层 第几次进入这个函数就是第几层
//    for (int i = start; i < nums.size(); ++i) {
//
//        //去除本层元素以及 保证前一个元素大于后面一个 注意用empty 好点 temp.back() 获取最后那个元素
//        if ((!temp.empty() && temp.back() > nums[i]) || uset.find(nums[i]) != uset.end())
//            continue;
//        uset.insert(nums[i]); // 记录这个元素在本层⽤过了，本层后⾯不能再⽤了
//
//        temp.push_back(nums[i]);
//        findSubsequencesBack1(nums, i + 1);
//        temp.pop_back();
//    }
//}


vector<vector<int>> findSubsequences(vector<int> &nums) {
    //sort(nums.begin(), nums.end());
    used.resize(nums.size() + 1);
    findSubsequencesBack(nums, 0);
    return ret;
}